package com.cn.codebrush.练习;

/**
 * @Author Boolean
 * @Date 2023/6/7 16:11
 * @Version 1.0
 */
public class Test1 {
    public static void main(String[] args) {

    }

    /*输入：s = "babad"
    输出："bab"
    解释："aba" 同样是符合题意的答案。*/
    public String longestPalindrome(String s) {
        String res = "";
        int n = s.length();
        boolean[][] dp = new boolean[n][n];

        for(int i=n-1;i>0;i--){
            for(int j=i;j<n;j++){
                if(s.charAt(i) == s.charAt(j) && (j-i<2 || dp[i+1][j-1])){
                    dp[i][j] = true;
                    res = res.length()>s.substring(i,j+1).length()?res:s.substring(i,j+1);
                }
            }
        }


        return res;

    }


}

